Section: New Results

Theoretical and Methodological Developments

Participants : Cédric Joncour, Andrew Miller, Arnaud Pêcher, Pierre Pesneau, Ruslan Sadykov, Gautier Stauffer, François Vanderbeck.

We made progress in the developement of theory and algorithms in the area of “Reformulation and Decomposition Approaches for MIP”, “Mixed Integer Nonlinear Programming”, and “Polyhedral Combinatorics and Graph Theory”.

Column Generation for Extended Formulations

Working in an extended variable space allows one to develop tight reformulations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can use projection tools to derive valid inequalities for the original formulation and implement a cutting plane approach. Or, one can approximate the reformulation, using techniques such as variable aggregation or by reformulating a submodel only. Such approaches result in outer approximation of the intended extended formulation. The alternative considered in [28] , [25] is an inner approximation obtained by generating dynamically the variables of the extended formulation. It assumes that the extended formulation stems from a decomposition principle: a subproblem admits an extended formulation from which an extended formulation for the original problem can be derived. Then, one can implement column generation for the extended formulation of the original problem by transposing the equivalent procedure for the Dantzig-Wolfe reformulation. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solution.

Our paper [28] , [25] revisits the column-and-row generation approach. Our purpose is to show light on this approach, to emphasize its wide applicability, and to present it with a new angle as a method that is natural when considering a problem reformulation based on any extended reformulation of a subproblem, whether it yields the subproblem integer hull or just an approximation of it. In the spirit of [80] , column-and-row generation is viewed herein as a generalization of standard column generation, the latter being based on a specific subproblem extended formulation. This generic view not only highlights the scope of applicability of the method, but it also leads to a more general termination condition than the traditional reduced cost criteria and to theoretically stronger dual bounds (observing that solving the integer subproblems yields Lagrangian dual bounds that might be tighter than the extended formulation LP bound). We highlight a key motivation for working in the extended space: there arises natural recombinations of previously generated columns into new subproblem solutions, which results in an acceleration of the convergence. We point out that lifting the master program in the variable space of the extended formulation can be done while carrying pricing in the compact variable space of the original formulation, using any oracle.

With [28] , [25] , we establishe the validity of the column-and-row generation algorithm in a form that encompass all special cases of the literature. The analysis therein should help practitioners to evaluate whether this alternative procedure has potential to outperform classical column generation on a particular problem. Our numerical experiments highlight a key observation: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence.

Primal Heuristics for Branch-and-Price

Our goal is to exploit global optimization decomposition approaches to retrieve very good feasible solution to large scale problem. This required extending primal heuristic paradigms to the context of dynamic generation of the variables of the model. We highlight an important fact: such generic tools typically performs better than problem specific meta-heursitics, in terms of solution quality and computing times. Based on our application specific experience with these techniques [65] , [67] , [86] , [87] , and on a review of generic classes of column generation based primal heuristics, in [58] , we are developping a full blown review of such techniques, completed with new methods and an extensive numerical study. This research is being carried on in collaboration with the membersof the associated team project, SAMBA.

Significant progress has been achieved in developing generic primal heuristics that made their way into commercial mixed integer programming (MIP) solvers. Extensions to the context of a column generation solution approach are considered by our team, in search for generic black-box primal heuristics for use in Branch-and-Price approaches. As the Dantzig-Wolfe reformulation is typically tighter than the original compact formulations, techniques based on rounding its linear programming solution have better chance to yield good primal solutions. The aggregated information built into the column definition and the price coordination mechanism provide a global view at the solution space that may be lacking in somewhat more “myopic” approaches based on compact formulations. However, the dynamic generation of variables requires specific adaptation of heuristic paradigms. We focus on “diving” methods and considered their combination with sub-MIPing, relaxation induced neighborhood search, and truncated backtracking using a Limited Discrepancy Search. These add-ons serves as local-search or diversification/intensification mechanisms. We also consider feasibility pump approaches. The methods are numerically tested on standard models such as Cutting Stock, Vertex Coloring, Generalized Assignment, Lot-Sizing, and Vehicle Routing problems.

Combining Bender's and Dantzig-Wolfe Decomposition

In the follow-up of [56] , [88] , [89] , [90] , we are finalizing our work on the combination of Dantzig-Wolfe and Bender's decomposition: Bender's Master is solved by column generation [91] . The application we considered is a multi-layer network design model arising from a real-life telecommunication application where traffic routing decisions imply the installation of expensive nodal equipment. Customer requests come in the form of bandwidth reservations for a given origin destination pair. Bandwidth requirements are expressed as a multiple of nominal granularities. Each request must be single path routed. Grooming several requests on the same wavelength and multiplexing wavelengths in the same optical stream allow the packing of more traffic. However, each addition or withdrawal of a request from a wavelength requires optical to electrical conversion for which a specific portal equipment is needed. The objective is to minimize the number of such equipment. We deal with backbone optical networks, therefore with networks with a moderate number of nodes (14 to 20) but thousands of requests. Further difficulties arise from the symmetries in wavelength assignment and traffic loading. Traditional multi-commodity network flow approaches are not suited for this problem. Four alternative models relying on Dantzig-Wolfe and/or Benders' decomposition are introduced and compared. The formulations are strengthened using symmetry breaking restrictions, variable domain reduction, zero-one decomposition of integer variables, and cutting planes. The resulting dual bounds are compared to the values of primal solutions obtained through hierarchical optimization and rounding procedures. For realistic size instances, our best approaches provide solutions with optimality gap of approximately 5% on average in around 2 hours of computing time.

Branching in Branch-and-Price: a generic scheme

Our innovative branching scheme, proposed for its compatible with the column generation procedure (it implies no structural modifications to the pricing problem) is now published in Mathematical Programming A [23] . The scheme proceeds by recursively partitioning the sub-problem solution set. Branching constraints are enforced in the pricing problem instead of being dualized in a Lagrangian way. The subproblem problem is solved by a limited number of calls to the provided solver. The scheme avoids the enumeration of symmetric solutions.

Strong Branching Inequalities for Convex Mixed Integer Nonlinear Programs

Strong branching is an effective branching technique that can significantly reduce the size of the branch-and-bound tree for solving Mixed Integer Nonlinear Programming (MINLP) problems. The focus of our paper [24] is to demonstrate how to effectively use discarded information from strong branching to strengthen relaxations of MINLP problems. Valid inequalities such as branching-based linearizations, various forms of disjunctive inequalities, and mixing-type inequalities are all discussed. The inequalities span a spectrum from those that require almost no extra effort to compute to those that require the solution of an additional linear program. In the end, we perform an extensive computational study to measure the impact of each of our proposed techniques. Computational results reveal that existing algorithms can be significantly improved by leveraging the information generated as a byproduct of strong branching in the form of valid inequalities.

Linear and Nonlinear Inequalities for a Nonseparable Quadratic Set

We described some integer-programming based approaches for finding strong inequalities for the convex hull of a quadratic mixed integer nonlinear set containing two integer variables that are linked by linear constraints. This study [31] was motivated by the fact that such sets appear can be defined by a convex quadratic program, and therefore strong inequalities for this set may help to strengthen the formulation of the original problem. Some of the inequalities we define for this set are linear, while others are nonlinear (specifically conic). The techniques used to define strong inequalities include not only ideas related to recent perspective reformulations of MINLPs, but also disjunctive and lifting arguments. Initial computational tests will be presented.

On the composition of convex envelopes for quadrilinear terms

Within the framework of the spatial Branch-and-Bound algorithm for solving Mixed-Integer Nonlinear Programs, different convex relaxations can be obtained for multilinear terms by applying associativity in different ways. The two groupings ((x1x2)x3)x4 and (x1x2x3)x4 of a quadrilinear term, for example, give rise to two different convex relaxations. In previous work, we proved that having fewer groupings of longer terms yields tighter convex relaxations. In this paper [35] , we give an alternative proof of the same fact and perform a computational study to assess the impact of the tightened convex relaxation in a spatial Branch-and-Bound setting.

Stable sets in claw-free graphs

A stable set is a set of pairwise non adjacent vertices in a graph and a graph is claw-free when no vertex contains a stable set of size three in its neighborhood. Given weights on the vertices, the stable set problem (a NP-hard problem in general) consists in selecting a set of pairwise non adjacent vertices maximizing the sum of the selected weights. The stable set problem in claw-free graphs is a fundamental generalization of the classic matching problem that was shown to be polynomial by Minty in 1980 (G. Minty. On maximal independent sets of vertices in claw-free graphs. J. Combinatorial Theory B, 28:284-304 (1980)). However, in contrast with matching, the polyhedral structure (i.e. the integer hull of all stable sets in a claw-free graph) is not very well understood and thus providing a `decent' linear description of this polytope has thus been a major open problem in our field.

We proposed a new algorithm to find a maximum weighted stable set in a claw-free graph [45] whose complexity is now drastically better than the original algorithm by Minty ($n^3$ versus $n^6$, where $n$ is the number of vertices). We also provided a description of the polyhedra in an extended space (i.e. using additional artificial variables) and an efficient procedure to separate over the polytope in polynomial-time [27] . Beside those main contributions, we published another papers on the strongly minimal facets of the polytope [22] .

We also published two survey papers on both the algorithmic and polyhedral aspects of the problem [32] , [16] .

Chvátal-Gomory rank of 0/1 polytopes

In [17] , we study the Chvátal-Gomory rank of 0/1 polytopes. The Chvàtal-Gomory procedure is a generic cutting plane procedure to derive the integer hull of polyhedra, and the rank is the number of iterations needed. We revisited a classic framework by Chvátal, Cook and Hartmann (V. Chv‡tal, W. Cook, and M. Hartmann. On cutting-plane proofs in combinatorial optimization. Linear Algebra and its Applications, 114/115:455-499 (1989)) to prove lower bounds on the CG-rank and we made it more accessible (the original framework was hard to apply). It allowed us to give a very simple construction and to improve the lower bound on the rank of general 0/1 polytopes (the previous weaker lower bound relied on a sophisticated existence theorem by Erdös). This result is important as it shed some new light on a supposedly well understood procedure.

The Circular-Chromatic number

Another central contribution of our team concerns the chromatic number of a graph (the minimum number of independent stable sets needed to cover the graph). We proved that the chromatic number and the clique number of some superclasses of perfect graphs is computable in polynomial time [19] , [18] .

We investigated the circular-chromatic number. It is a well-studied refinement of the chromatic number of a graph (designed for problems with periodic solutions): the chromatic number of a graph is the integer ceiling of its circular-chromatic number. Xuding Zhu noticed in 2000 that circular cliques are the relevant circular counterpart of cliques, with respect to the circular chromatic number, thereby introducing circular-perfect graphs, a super-class of perfect graphs.

We proved that the chromatic number of circular-perfect graphs is computable in polynomial time [73] , thereby extending Grötschel, Lovász and Schrijver's result to the whole family of circular-perfect graphs. We gave closed formulas for the Lovász Theta number of circular-cliques (previously, closed formulas were known for circular-cliques with clique number at most 3 only), and derived from them that the circular-chromatic number of circular-perfect graphs is computable in polynomial time [34] .